package leetcode.动态规划;

public class Leetcode1406 {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] preSum = new int[n+1];
        for (int i = 0; i < n+1; i++) {
            preSum[i+1] = preSum[i]+stoneValue[i];
        }
        if(dfs(stoneValue,0,preSum)>=0){
            return "Alice";
        }else{
            return "Bob";
        }

    }

    public int dfs(int[] stoneValue,int left,int[] preSum){
        if(left==stoneValue.length){
            return 0;
        }
        if(stoneValue.length-left<=3){
            return preSum[stoneValue.length] - preSum[left];
        }
        int max = Integer.MIN_VALUE;
        for(int i = left;i<left+3&&i<stoneValue.length;i++){
            int chooseLeft = preSum[left+i]-preSum[left];
            max = Math.max(max,chooseLeft-dfs(stoneValue,left+i,preSum));
        }
        return max;
    }
}
